package datamining;

import java.util.BitSet;
import java.util.HashSet;
import java.util.Set;


public class SubsetCombin {

private static String[] array;
private static BitSet startBitSet; 
private static BitSet endBitSet; 
private static Set<Set<String>> properSubset; 


public static Set<Set<String>> getCombin(int n, Set<String> itemSet) {
   String[] array = new String[itemSet.size()];
   SubsetCombin.array = itemSet.toArray(array);
   properSubset = new HashSet<Set<String>>();
   startBitSet = new BitSet();
   endBitSet = new BitSet();

  
   for (int i=0; i<n; i++) {
    startBitSet.set(i, true);
   }

   for (int i=array.length-1; i>=array.length-n; i--) {
    endBitSet.set(i, true);
   }
  
 
   get(startBitSet);   
  
   while(!startBitSet.equals(endBitSet)) {
    int zeroCount = 0;  
    int oneCount = 0; 
    int pos = 0; 
   
   
    for (int i=0; i<array.length; i++) {
     if (!startBitSet.get(i)) {
      zeroCount++;
     }
     if (startBitSet.get(i) && !startBitSet.get(i+1)) {
      pos = i;
      oneCount = i - zeroCount;
      // 
      startBitSet.set(i, false);
      startBitSet.set(i+1, true);
      break;
     }
    }
    // 
    int counter = Math.min(zeroCount, oneCount);
    int startIndex = 0;
    int endIndex = 0;
    if(pos>1 && counter>0) {
     pos--;
     endIndex = pos;
     for (int i=0; i<counter; i++) {
      startBitSet.set(startIndex, true);
      startBitSet.set(endIndex, false);
      startIndex = i+1;
      pos--;
      if(pos>0) {
       endIndex = pos;
      }
     }
    }
    get(startBitSet);
   }  
   return properSubset;
}

/**
*/
private static void get(BitSet bitSet) {
   Set<String> set = new HashSet<String>();
   for(int i=0; i<array.length; i++) {
    if(bitSet.get(i)) {
     set.add(array[i]);
    }
   }
   properSubset.add(set);
}

public static void main(String[] args) throws Exception {
        
        Set<String> itemSet = new HashSet<String>();
        Set<Set<String>> res = new HashSet<Set<String>>();
        itemSet.add("a");
        itemSet.add("b");
        itemSet.add("c");
        itemSet.add("d");
        res = SubsetCombin.getCombin(3, itemSet);
     
    }
}